/*
 * =====================================================================================
 *
 *       Filename:  1007_DNAsorting.cc
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  09/10/2012 11:21:46 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */
#include	<stdio.h>

typedef struct node_s
{
    char str[56];
    int  sortness;
}Node;

Node nodeArr[104];
Node* nodePtrArr[104];
//how to get the un sortedness
//use the simple method with n * n
/*
int getUnSortedNess(const char *str, int len)
{
    int cnt = 0;
    for (int i = 0; i < len-1; ++i)
        for (int k = i+1; k < len; ++k)
            if (str[i] > str[k])
                ++cnt;
    return cnt;
}
*/

//learn from a boy, in O(n) time to caculate the reverse degree
int count_inver(const char *str, int len)
{
        int i;  
        int cnt = 0;
        int a[4] = {0};
        for(i = len - 1; i >= 0; i--) {
                switch (str[i]) {
                        case 'A':
                                a[1]++; 
                                a[2]++; 
                                a[3]++; 
                                break;  
                        case 'C':
                                a[2]++; 
                                a[3]++; 
                                cnt += a[1];
                                break;  
                        case 'G':
                                a[3]++; 
                                cnt += a[2];
                                break;  
                        case 'T':
                                cnt += a[3];
                }
        }
        return cnt;
}

//qsort is not so stable
void myInsertSort(Node *ptrArr[], int len)
{
    Node *bak;
    for (int i = 1; i < len; ++i)
    {
        bak = ptrArr[i];
        int k;
        for (k = i - 1; k >= 0; --k)
            if (bak->sortness < ptrArr[k]->sortness)
                ptrArr[k+1] = ptrArr[k];
            else 
                break;
        ptrArr[k+1] = bak;
    }
}

int main(int argc, char *argv[])
{
    int nn, mm;
    while (scanf("%d%d", &nn, &mm) == 2)
    {
        for (int i = 0; i < mm; ++i)
        {
            scanf("%s", nodeArr[i].str);
            nodeArr[i].sortness = count_inver(nodeArr[i].str, nn);
            nodePtrArr[i] = &nodeArr[i];
        }
        myInsertSort(nodePtrArr, mm);
        for (int k = 0; k < mm; ++k)
            printf ( "%s\n", nodePtrArr[k]->str);
    }
    return 0;
}
